<?
include_once "SortHelper/SortHelper.php";
/**
 * 插入排序
 */
//第1，待排序数组：[5,4,7,26,14,8,65,77,53]
//第2，如果前面的数 > 后面的数 就把前面的数覆盖到后面：[5,5,7,26,14,8,65,77,53] //这里把 4 先拿出来，然后往前找( j-- )看有没有比4大的数
//第3，再把值给到最后一个索引的位置：[4,5,7,26,14,8,65,77,53]
//第4，然后继续下一个数字判断（循环）
function insertSort(&$arr)
{
    $arr_len = count($arr);
    if ($arr_len <= 0) {
        return [];
    }

    for ($i = 0; $i < $arr_len; $i++) { 

        //默认第一个已经排序好了 -- 待插入的值
        $value = $arr[$i];

        //如果前面的数 > 后面的数 就把前面的数覆盖到后面
        for ($j = $i; $j > 0 && $arr[$j - 1] > $value; $j--) { 
            //把前面的数循环赋值给后面的数
            $arr[$j] = $arr[$j - 1];
        }
        //全部赋值完以后，再把值给到最后一个索引的位置
        $arr[$j] = $value;
    }
}

$start = intval(microtime(true) * 1000);
$sortarr = [100,4,6,2,59,67,57,0,45,71,82];
insertSort($sortarr);
$str = '';
foreach ($sortarr as $value) {
    $str .= $value.',';
}
echo $str;
$endtime = intval(microtime(true) * 1000);
echo '排序耗时：'.($endtime - $start).'ms'."\n";